package hacker_rank.oct13;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Period {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			String[] tmp = br.readLine().split(" ");

			solve(Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]),
					Integer.parseInt(tmp[2]));

		}
	}

	private static void solve(int a, int b, int m) {
		int res = 1;
		PseudoComplex pc = new PseudoComplex(a, b);

		for (;;) {
			if (pc.isZero()) {
				System.out.println(-1);
				return;
			}
			if (pc.abs() == 1) {
				System.out.println(res);
				return;

			}
			pc = pc.oper(new PseudoComplex(a, b), m);
		//	System.out.println(pc.abs());

			res++;
		}
		

	}

	static class PseudoComplex {
		long re;
		long im;

		PseudoComplex(long re, long im) {
			this.re = re;
			this.im = im;
		}

		public boolean isZero() {
			if (this.re == 0 && this.im == 0)
				return true;
			return false;
		}

		PseudoComplex oper(PseudoComplex b, long m) {
			PseudoComplex a = this;
			long real = ((a.re * b.re) + (5 * a.im * b.im));
			long imag = ((a.re * b.im) + (a.im * b.re));
			//System.out.printf("%d %d\n", real, imag);
			return new PseudoComplex(real, imag);
		}

		public double abs() {
			/*if (this.im == 0)
				return this.re;
			return Integer.MAX_VALUE; */
			return Math.sqrt(this.re * this.re + (5 * this.im * this.im));
		}
	}
}
